package hzk.codex2016.sort;

class MaxHeaps {

	public static void siftDown(int[] a, int begin, int end) {
		int dad = begin, son, t;
		while ((son = dad * 2 + 1) < end) {
			if (son + 1 < end && a[son + 1] > a[son])
				son++;
			if (a[dad] < a[son]) {
				t = a[dad];	a[dad] = a[son]; a[son] = t;
				dad = son;
			} else {
				break;
			}
		}

	}

	public static void buildAndSort(int[] a) {
		int t, n = a.length;
		// build
		for (int i = n / 2 - 1; i >= 0; i--) {
			siftDown(a, i, n);
		}
		// sort
		while (n-- > 0) {
			t = a[0]; a[0] = a[n]; a[n] = t;
			siftDown(a, 0, n);
		}

	}

}

public class HeapSort implements Sorter {

	public void sort(int[] arr) {
		MaxHeaps.buildAndSort(arr);
	}

	public static void main(String[] args) {
		Sorter s = new HeapSort();
		for (int i = 1; i < 10; i++) {
			Arrs.test(s, i);
		}
		for (int i = 100; i <= 110000; i *= 10) {
			Arrs.test(s, i);
		}
		for (int i = 1; i <= 5; i++) {
			Arrs.test(s, 111000);
		}
	}

}
